package com.zk.algorithm.sort;

import com.zk.algorithm.Utils;

/**
 * 快速排序
 */
public class QuickSort {

    /**
     * {10,80,30,90,40,50,[70]}
     *
     * @param array
     * @param low
     * @param high
     * @return
     */
    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1; // 这个指针之前的元素全是小于 pivot 元素的

        for (int j = low; j <= high - 1; j++) {

            if (array[j] <= pivot) { // 当前元素小于 pivot
                i++; // 小于 pivot 元素的指针 + 1，代表又多了一个元素
                Utils.swap(array, i, j);
            }

        }

        Utils.swap(array, i + 1, high);

        return i + 1;
    }

    private void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(array, low, high);

            quickSort(array, low, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, high);
        }
    }

    public void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public static void main(String...args) {
        int[] array = new int[] { 10,80,30,90,40,50,70 };
        new QuickSort().quickSort(array);
        Utils.println(array);
    }

}
